10867. Maximum in unimodal sequence
Sequence ai is called unimodal if there exists
such index p that a1 < a2 < ... < ap and ap > ap+1
> ... > an. Value ap is maximum in this sequence. You
must find this value.
Input. The first line contains the size of array n (n ≤ 106). The next line contains n positive
integers that represent a unimodal sequence. Numbers in array do not exceed 109.
Output. Print the maximum element is the unimodal sequence.
|
Sample
input 1 |
Sample
output 1 |
|
10 2 4 7 12 18 19 16
11 8 3 |
19 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
6 3 5 7 11 15 17 |
17 |
SOLUTION
ternary search
Algorithm analysis
Let’s
find the maximum in a unimodal sequence using ternary search.
Divide the current search interval [left; right] with
points a and b into three equal parts:
·
a = left + (right – left)
/ 3;
·
b = left + 2 * (right – left)
/ 3;
When searching for a maximum if:
·
m[a] < m[b], then continue the search on the segment [a; right];
·
m[a] ≥ m[b], then continue the search on the segment [left; b];
Example
Consider the first test. Let’s execute the first iteration of the
ternary search.
Segment [left;
right] = [0; 9] is divided with points a = 3 and b
= 6 into three equal parts. Since m[a]
< m[b], we continue the search on the interval [a; right] = [3; 9].
Algorithm realization
Store
the input sequence in the array m.
#define MAX 1000001
int m[MAX];
The
function ternary_search returns the largest element in
the unimodal sequence m[left;
right].
int ternary_search(int left, int right)
{
If the
sequence contains no more than three elements, then find the maximum among them
using the full search.
if (right - left < 3)
{
int res = m[left++];
while (left <= right)
res = max(res, m[left++]);
return res;
}
Divide the
segment [left; right] with
points a and b into
three equal parts.
int a = left + (right - left) / 3;
int b = left + 2 * (right - left) / 3;
Compare m[a] and m[b]. Depending on the result, continue the search either
on the segment [a;
right], or on the segment [left; b].
if (m[a] < m[b]) return ternary_search(a, right);
return ternary_search(left, b);
}
The main
part of the program. Reading the input array.
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &m[i]);
Start a
ternary search and print the largest element in the unimodal sequence.
printf("%d\n", ternary_search(0, n - 1));